package graph.base;

import linear.Queue;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Graph {
    // 顶点数量
    private final int V;
    // 边数量
    private int E;
    // 邻接表
    private Queue<Integer>[] adj;

    public Graph(int v) {
        // 初始化顶点数量
        V = v;
        // 初始化边
        E = 0;
        // 初始化邻接表
        adj = new Queue[v];
        // 初始化
        for (int i = 0; i < v; i++) {
            adj[i] = new Queue<>();
        }
    }

    // 获取顶点数量
    public int V() {
        return V;
    }

    // 获取边数
    public int E() {
        return E;
    }

    // 添加一条边
    public void addEdge(int v, int w) {
        adj[v].enqueue(w);
        adj[w].enqueue(v);
        E++;
    }

    // 获取顶点v的所有相邻顶点
    public Queue<Integer> adj(int v) {
        return adj[v];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(Graph.class.getClassLoader().getResourceAsStream("traffic_project.txt")));
        //读取城市数目，初始化Graph图
        int number = Integer.parseInt(reader.readLine());
        Graph g = new Graph(number);
        //读取已经修建好的道路数目
        int roadNumber = Integer.parseInt(reader.readLine());
        for (int i = 0; i < roadNumber; i++) {
            String line = reader.readLine();
            int p = Integer.parseInt(line.split(" ")[0]);
            int q = Integer.parseInt(line.split(" ")[1]);
            g.addEdge(p, q);
        }

        //根据图G和顶点9构建图的搜索对象
        //BreadthFirstSearch search = new BreadthFirstSearch(G,9);
        DepthFirstSearch search = new DepthFirstSearch(g, 9);
        boolean flag1 = search.marked(10);
        boolean flag2 = search.marked(8);
        System.out.println("9号城市和10号城市是否已相通：" + flag1);
        System.out.println("9号城市和8号城市是否已相通：" + flag2);

    }

}
